The present invention relates generally to communications systems, and more particularly to methods for demodulating and decoding encoded data bits transmitting in a code division multiple access (CDMA) system.
Various communication systems are known in the art. In many systems an information signal is modulated onto a carrier signal and transmitted from a first location to a second location. At the second location, the information signal is demodulated and recovered.
Typically, the communication path used by such systems has various limitations, such as bandwidth. As a result, there are upper practical limitations that restrict the quantity of information that can be supported by the communication path over a given period of time. Various modulation techniques have been proposed that effectively increase the information handling capacity of the communication path as measured against other modulation techniques.
One modulation technique is M-ary quadrature amplitude modulation (QAM). QAM provides a constellation of an M number of modulation values (distinguished from one another by each having a different combination of phase and amplitude) wherein each constellation point represents a plurality of information bits. In order to achieve greater spectral efficiency in CDMA systems, for example, higher order modulations are used. In general, the number of bits that are represented by each symbol in an M-ary QAM system is equal to log M. For example, 16 QAM uses 16 distinct constellation points (four points in each quadrant of a complex Cartesian plane having I and Q axes) that each represent log216 or four information bits. Another example is 64-QAM wherein 64 constellation points each represent a combination of log264 or six information bits.
FIG. 1 illustrates a constellation for a 64-QAM communication system that is a map of 64 points each representing a combination of six bits on the complex plane defined by a horizontal axis representing the real portions (i.e., I) and a vertical axis representing imaginary portions (i.e., Q) of a complex number. Transmitted QAM information symbols on a communication channel (and the pilot and sync symbols as well) are discrete packets of a carrier signal modulated to convey information using both the amplitude and phase-angle displacement of the carrier from some reference. QAM information symbols are represented on the constellation of FIG. 1 as complex quantities represented as vectors having both magnitude (represented as length or distance from origin) and phase angles xcfx86 (angles measured with respect to one of the axes). In a 64-QAM system, having 64 different magnitude and phase angle combinations that correspond to 64 different possible bit patterns of six binary digits (which bits are from a serial stream of bits from an information source), each of the 64 points on the constellation is identified as representing one combination of six bits.
A vector 100 (expressed in rectangular coordinates as 5I+5Q and having a length=(52+52)/2 and a phase angle 102 equal to the arc tangent of 5/5 or forty-five degrees with respect to the real axis), points to the point 104 in the constellation. This point is shown in FIG. 1 as representing the series of six binary digits (i.e., 000000). Another QAM symbol represented by point 106 (xe2x88x921Ixe2x88x921Q) is illustrated in this constellation and represents another series of six binary digits (i.e., 110011).
For any modulation scheme, the demodulator preferably should provide the decoder with the log-likelihood ratio (LLR) of the received encoded bits. As shown in FIG. 2, a receiver 200 in a CDMA system includes a log-likelihood ratio calculator 202 that receives demodulated symbols from a demodulator 204 and calculates a LLR for each bit of the demodulated symbols. The decoder 206 receives the LLR""s calculated by the log-likelihood ratio calculator 202 and decodes the individual bits based on the received LLR""s.
When two-dimensional modulations (i.e., having I and Q components) yield spectral efficiencies greater than 2 bps/Hz, each encoded bit cannot be mapped to an orthogonal symbol component. As a result, bit LLR""s must be calculated from Euclidean distances between the demodulated symbol and the constellation symbols. The LLR of each actual jth bit associated with a symbol y received at time k (referred to as yi) is determined by the following relationship:                               LLR          ⁡                      (                          u                              k                ,                j                                      )                          =                  log          ⁢                      {                                                                                P                    (                                                                  u                                                  k                          ,                          j                                                                    =                      0                                        "RightBracketingBar"                                    ⁢                                      y                    k                                                  )                                                                                  P                    (                                                                  u                                                  k                          ,                          j                                                                    =                      1                                        "RightBracketingBar"                                    ⁢                                      y                    k                                                  )                                      }                                              (        1        )            
where uk,j is the hypothesis jth bit value of the symbol u at time k and P represents the probability that the jth bit of uk is a binary value of 0 or 1 given that yk is the received symbol. This equation reduces to the expression:                               LLR          ⁡                      (                          u                              k                ,                j                                      )                          =                  log          ⁢                      {                                                                                ∑                                                                                            u                          k                                                ⁢                                                  u                                                      k                            ,                            j                                                                                              =                      0                                                        ⁢                                      xe2x80x83                                    ⁢                                                            P                      (                                              y                        k                                            "RightBracketingBar"                                        ⁢                                          u                      k                                                                      )                                                                                  ∑                                                                                            u                          k                                                ⁢                                                  u                                                      k                            ,                            j                                                                                              =                      1                                                        ⁢                                      xe2x80x83                                    ⁢                                                            P                      (                                              y                        k                                            "RightBracketingBar"                                        ⁢                                          u                      k                                                                      )                                      }                                              (        2        )            
assuming that all transmitted symbols are equiprobable. The probability P is represented by the following relationship assuming a perfect channel correction, such that the real and imaginary components are independent:
P(yk|uk)=p(yki,yki|uki,uki)=p(yki|uki)p(yki|uki)xe2x80x83xe2x80x83(3) 
Assuming additive Gaussian noise, the above equation reduces to the following expression:                                                         P              (                              y                k                            "RightBracketingBar"                        ⁢                          u              k                                )                =                              1                          2              ⁢                              πσ                2                                              ⁢                      exp                                          -                                  D                  k                  2                                                            2                ⁢                                  σ                  2                                                                                        (        4        )            
where Dk2 is the squared Euclidean distance between the received symbol and the hypothesis symbol and "sgr"2 is the variance of the Gaussian noise. Accordingly, the squared Euclidean distance Dk2 is calculated by summing the squares of the differences between the received and hypothesis symbol of both the real (r) and imaginary (i) components as represented by the following relationship:
Dk2=|ykxe2x88x92uk|2=(ykixe2x88x92uki)2+(ykixe2x88x92uki)2xe2x80x83xe2x80x83(5) 
Substituting equation (4) into equation (2) allows calculation of the LLR based on the squared Euclidean distances and yields the following expression:                               LLR          ⁡                      (                          u                              k                ,                j                                      )                          =                              log            ⁢                                          ∑                                                                            u                      k                                        ⁢                                          u                                              k                        ,                        j                                                                              =                  0                                            ⁢                              ⅇ                                                      -                                          D                      k                      2                                                                            2                    ⁢                                          σ                      2                                                                                                    -                      log            ⁢                                          ∑                                                                            u                      k                                        ⁢                                          u                                              k                        ,                        j                                                                              =                  1                                            ⁢                              ⅇ                                                      -                                          D                      2                                                                            2                    ⁢                                          σ                      2                                                                                                                              (        6        )            
This expression may be approximated by simply taking the difference between the minimum squared distances between the received symbol and the hypothesis symbol having respective bit values of 1 and 0. Thus, equation (6) may be reduced to the following expression to approximate the LLR:                               LLR          ⁡                      (                          u                              k                ,                j                                      )                          =                                            min                                                                    u                    k                                    ⁢                                      u                                          k                      ,                      j                                                                      =                1                                      ⁢                          [                              D                k                2                            ]                                -                                    min                                                                    u                    k                                    ·                                      u                                          k                      ,                      j                                                                      =                0                                      ⁢                          [                              D                k                2                            ]                                                          (        7        )            
where the LLR of a bit uk . . . j in a symbol is found by computing the difference of the minimum distance between the received symbol and a QAM constellation point where that particular bit equals one and the minimum distance between the received symbol and a QAM constellation point where that particular bit equals zero. In M-ary QAM systems the M number of symbols is equal to 2m with m being the number of bits per symbol. Hence, a m number of LLR calculations are required per modulation symbol (i.e., finding the LLR for each of the m number of bits in the symbol). In order to determine the m number of LLR calculations, a M number of squared Euclidian distances (D2) must first be determined between the received QAM symbol and each of the QAM symbols in the QAM constellation of symbols. Given the above mathematical operations, the calculation of LLR values for each received modulation symbol require a M number of squared Euclidean distance calculations (i.e., D2 calculations, each of which involve 2 multiplication operations and an addition operation), a M number of comparison/selections per bit to determine the minimum squared Euclidean to the particular bit values of one and zero for all of the m bits in the symbol (i.e. the number of min D2 values where u=1(M/2 comparison/selections and the number of min D2 values where u=0 (M/2 comparison/selections), the total then multiplied by the m number of total bits in the symbol and a m number of addition operations for determining the difference between the values as shown in Equation (7) above. Accordingly, the total number of operations required per received QAM modulation symbol is 2M multiplication operations plus mM comparison/selection operation plus a M+m number of addition operations.
For purposes of illustrating reduced frame processing time, it is assumed that a clock rate for a CDMA system is 32xc3x971.2288 MHz, or 39.3216 MHz, although the teachings of the present application are advantageous at any number of different clock rates. A multiplication operation typically requires 2 clock cycles to complete, addition operations 1 clock cycle and comparison/selection operations 2 clock cycles. Thus, for example, the time required to process a frame with 64-QAM modulation containing 5376 symbols with 6 bits per symbol, would be approximately 150 ms. This time period becomes problematic because it is much greater than the 5 to 20 ms frame turn around time required for high speed data channels. Techniques such as parallelization and pipelining may be used to reduce calculation time, but are nonetheless insufficient to reduce the receiver throughput rate down to the order of a frame turn around time in a high speed data channel.
Accordingly, there is a need for reduction of computation time for LLR""s to the order of a frame time in a receiver that bit decodes QAM modulated symbols, especially for higher orders such as 64-QAM.